package solution;

import java.util.ArrayList;
import java.util.HashSet;

/**
 * <a href="https://www.nowcoder.com/practice/a43a2b986ef34843ac4fdd9159b69863?tpId=188&&tqId=38618&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking">
 * NC42 有重复项数字的所有排列</a>
 *
 * @author or2
 * @Description 给出一组可能包含重复项的数字，返回该组数字的所有排列。
 * @create 2021年09月11日 时间: 22:11
 */
public class PermuteUnique {
    /**
     * 存放 答案
     */
    private final ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
    /**
     * 存放 遍历时 当前答案变量
     */
    private final ArrayList<Integer> layer = new ArrayList<>();
    /**
     * 当前状态下 移除的变量
     */
    private final HashSet<Integer> remove = new HashSet<>();

    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
//        递归终止条件
        if (remove.size() == num.length) {
            ArrayList<Integer> ansLayer = new ArrayList<>(layer);
            ans.add(ansLayer);
            return ans;
        }
//        防止重复添加
        HashSet<Integer> multi = new HashSet<>();
        for (int i = 0; i < num.length; i++) {
//            该元素已被上层使用
            if (!remove.contains(i)) {
//                防止重复添加
                if (multi.contains(num[i])) {
                    continue;
                }
                multi.add(num[i]);
//                正式开始搜索
                layer.add(num[i]);
                remove.add(i);
                permuteUnique(num);
//                递归回来时, 恢复状态 - 回溯
                layer.remove(layer.size() - 1);
                remove.remove(i);
            }
        }
        return ans;
    }
}
